package oct2013;

public class GasStation {
	public int canCompleteCircuit(int[] gas, int[] cost) {
		int n = gas.length;
		for (int i = 0; i < n; ++i) {
			int sum = 0;
			for (int j = i; j < i + n; ++j) {
				int idx = j % n;
				sum += gas[idx] - cost[idx];
				if (sum < 0) {
					i = j;
					break;
				}
			}
			if (sum >= 0)
				return i;
		}
		return -1;
	}
}
